package practice.sort;

/**
 * 插入排序
 */
public class InsertionSort extends SortAdaptor {

    public static void main(String[] args) {
        int[] nums = {3,9,10,2,3,123,239,4,13,443,23,29};
        sort2(nums);
        for (int num :
                nums) {
            System.out.print(num + " ");
        }
    }
    /**
     * 插入时依次交换
     * @param nums
     */
    public static void sort(int[] nums) {
        if (nums.length < 0) {
            return;
        }
        for (int i = 1; i < nums.length; i++) {
            for (int j = i; j > 0 && nums[j] < nums[j - 1]; j--) {
                swap(nums, j, j - 1);
            }
        }
    }

    /**
     * 插入时较大的后移，最后再交换
     * @param nums
     */
    public static void sort2(int[] nums) {
        if (nums.length < 0) {
            return;
        }
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            int j = i;
            for (; j > 0 &&  num < nums[j-1]; j--) {
                nums[j] = nums[j-1];
            }
            nums[j] = num;
        }
    }
}
